In just the past few years, algorithms from the relatively nascent field of machine learning have been widely applied for many types of practical applications, resulting in technologies such as self-driving vehicles, improved Internet search engines, speech, audio, and/or visual recognition systems, human health data and genome analysis, recommendation systems, fraud detection systems, etc. The growth of the use of these algorithms has in part been fueled by recent increases in the amount and types of data being produced by both humans and non-humans. Thus, as the increased amount of data available for analysis has skyrocketed, so too has the interest in machine learning.
In many different contexts, machine learning algorithms are commonly being implemented using large matrices. Further, many of these matrices are “sparse” matrices in that they have a significant number of “empty” or “background” values—e.g., zero values. For example, social graphs can be modeled as matrices (e.g., “adjacency matrices”) that have as many rows and columns as there are people in the data set, where the elements in the cells of the matrix represent some information about the connections between each pair of people.
When storing and utilizing sparse matrices, it is useful (and sometimes, strictly necessary) to use specialized algorithms and data structures that can take advantage of the sparse structure of the matrix. This is because performing matrix operations using regular dense-matrix structures and algorithms will be quite inefficient when applied to large, sparse matrices as processing and storage resources are effectively “wasted” due to the existence of the substantial amount of zeroes. Thus, sparse data can be easily compressed to require significantly less storage, and particular algorithms and computing architectures can be implemented to accommodate these compressed structures.
However, algorithms involving matrix manipulations, which include many machine learning algorithms, tend to be computationally expensive, as they can involve performing huge numbers of non-trivial operations with huge amounts of data. As a result, it is extremely important to implement these algorithms as efficiently as possible, as any small inefficiency is quickly magnified due to the large scale of computation.
Accordingly, techniques and processing architectures that can enhance the performance of these types of operations involving sparse matrix data are strongly desired.